The present invention pertains to the digital communication art and, more particular, to a method, and apparatus for the coding and decoding of digital data.
Coding and decoding schemes for purposes of correcting errors in the transmission of digital data are well-known, especially in the computer and digital data communication art. Errors may occur whenever a stream of digital transmission bits, e.g. a sequence of logic "0" or "1" levels, is transmitted over a channel subject to noise interference. Such errors may be classified into two categories, namely, random errors and burst errors. Random errors are those errors which occur sporadically and, generally, do not obliterate more than a few bits in succession. Burst errors are those caused by interference which exists over several successive bit intervals.
The prior art has developed three basic coding schemes to minimize or eliminate errors in transmitted digital data. These systems are block codes, convolutional codes, and interleaving schemes.
In both burst and convolutional codes, parity bits are generated and transmitted along with the information bits. These parity bits are related to the information bits in a predetermined manner such that upon reception errors in transmission may be found. In block codes, the parity bits and information bits are sent in distinct blocks. Such block codes are particularly effective at minimizing burst errors.
Convolutional coding schemes have been developed which convolve the parity bits with the information bits. These sytems are particularly effective for eliminating random errors.
Interleaving schemes recognize that if sequential characters of information are transmitted, a burst error may destroy an entire character. Therefore, each character is broken up into several portions and these portions are interleaved such that a burst error will tend to obliterate only portions of characters whereby a suitable decoding scheme may restore the entire character.
One prior art approach has been to combine a block coding scheme with an interleaving scheme. While this system exhibits superior error correcting capabilities over any one of the prior art systems, it has a principle drawback, namely, it can only accept characters of certain defined lengths.